//
//  Code4.swift
//  cnswift-demo
//
//  Created by YangWei on 2021/1/10.
//  Copyright © 2021 YangWei. All rights reserved.
//

import UIKit

/**
 4. 寻找两个正序数组的中位数
 
 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

  

 示例 1：

 输入：nums1 = [1,3], nums2 = [2]
 输出：2.00000
 解释：合并数组 = [1,2,3] ，中位数 2
 示例 2：

 输入：nums1 = [1,2], nums2 = [3,4]
 输出：2.50000
 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 示例 3：

 输入：nums1 = [0,0], nums2 = [0,0]
 输出：0.00000
 示例 4：

 输入：nums1 = [], nums2 = [1]
 输出：1.00000
 示例 5：

 输入：nums1 = [2], nums2 = []
 输出：2.00000
  

 提示：

 nums1.length == m
 nums2.length == n
 0 <= m <= 1000
 0 <= n <= 1000
 1 <= m + n <= 2000
 -106 <= nums1[i], nums2[i] <= 106

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Code4: Base {
    
    func run() {
        // 测试用例
        runCase([1], [2, 3], 2.0)
        runCase([1, 2], [3, 4], 2.5)
        runCase([0, 0], [0, 0], 0.0)
        runCase([], [1], 1)
        runCase([2], [], 2)
    }
    
    func runCase(_ nums1: [Int], _ nums2: [Int], _ result: Double) {
        let result1 = findMedianSortedArrays(nums1, nums2)
        if result1 == result {
            print("✅ \(nums1) 和 \(nums2) 的中位数 = \(result1)")
        } else {
            print("❌ \(nums1) 和 \(nums2) 的中位数 != \(result1)")
        }
    }
    
    func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
        
        var middleValue = 0.0
        
        let nums1Count = nums1.count
        let nums2Count = nums2.count
        let count = nums1Count + nums2Count
        
        if nums1Count == 0 && nums2Count == 0 {
            middleValue = 0.0
        }
        else if nums1Count == 0 {
            middleValue = findMiddleValue(nums:nums2)
        }
        else if nums2Count == 0 {
            middleValue = findMiddleValue(nums: nums1)
        }
        else {
            var num1Copy = [Int](nums1)
            var num2Copy = [Int](nums2)
            var combineNums = [Int]()
            
            for _ in 0..<count {
                if num1Copy.first == nil && num2Copy.first == nil {
                    middleValue = findMiddleValue(nums: combineNums)
                    break
                }
                else if num1Copy.first == nil {
                    combineNums.append(contentsOf: num2Copy)
                    middleValue = findMiddleValue(nums:combineNums)
                    break
                }
                else if num2Copy.first == nil {
                    combineNums.append(contentsOf: num1Copy)
                    middleValue = findMiddleValue(nums: combineNums)
                    break
                }
                else {
                    if num1Copy.first! > num2Copy.first! {
                        combineNums.append(num2Copy.first!)
                        num2Copy.removeFirst()
                    }
                    else if num1Copy.first! < num2Copy.first! {
                        combineNums.append(num1Copy.first!)
                        num1Copy.removeFirst()
                    }
                    else {
                        combineNums.append(num1Copy.first!)
                        combineNums.append(num2Copy.first!)
                        num1Copy.removeFirst()
                        num2Copy.removeFirst()
                    }
                }
            }
            middleValue = findMiddleValue(nums: combineNums)
        }
        
        return middleValue
    }
    
    func findMiddleValue(nums: [Int]) -> Double {
        
        let count = nums.count
        if count == 0 {
            return 0.0
        }
        
        let remainder = count % 2
        
        if remainder == 0 {
            // 偶数
            return Double(nums[count / 2 - 1] + nums[count / 2]) / 2.0
        } else {
            // 奇数个数
            return Double(nums[(count - 1) / 2])
        }
    }
}
